<!doctype html>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>零钱兑换 - 动态规划算法详解</title>
    <link rel="stylesheet" href="https://cdn.staticfile.org/font-awesome/6.4.0/css/all.min.css">
    <link rel="stylesheet" href="https://cdn.staticfile.org/tailwindcss/2.2.19/tailwind.min.css">
    <link href="https://fonts.googleapis.com/css2?family=Noto+Serif+SC:wght@400;500;600;700&family=Noto+Sans+SC:wght@300;400;500;700&display=swap" rel="stylesheet">
    <script src="https://cdn.jsdelivr.net/npm/mermaid@latest/dist/mermaid.min.js"></script>
    <style>
        body {
            font-family: 'Noto Sans SC', Tahoma, Arial, Roboto, "Droid Sans", "Helvetica Neue", "Droid Sans Fallback", "Heiti SC", "Hiragino Sans GB", Simsun, sans-serif;
        }
        .serif-font {
            font-family: 'Noto Serif SC', serif;
        }
        .gradient-text {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
            -webkit-background-clip: text;
            -webkit-text-fill-color: transparent;
            background-clip: text;
        }
        .hero-gradient {
            background: linear-gradient(135deg, #667eea 0%, #764ba2 100%);
        }
        .card-hover {
            transition: all 0.3s ease;
        }
        .card-hover:hover {
            transform: translateY(-5px);
            box-shadow: 0 20px 40px rgba(0,0,0,0.1);
        }
        .code-block {
            background: #1e1e1e;
            border-radius: 12px;
            overflow: hidden;
        }
        .code-header {
            background: #2d2d2d;
            padding: 12px 20px;
            display: flex;
            align-items: center;
            justify-content: space-between;
        }
        .code-dots {
            display: flex;
            gap: 8px;
        }
        .dot {
            width: 12px;
            height: 12px;
            border-radius: 50%;
        }
        .dot-red { background: #ff5f56; }
        .dot-yellow { background: #ffbd2e; }
        .dot-green { background: #27c93f; }
        pre {
            margin: 0;
            padding: 20px;
            overflow-x: auto;
        }
        code {
            font-family: 'Consolas', 'Monaco', 'Courier New', monospace;
            color: #d4d4d4;
            line-height: 1.6;
        }
        .keyword { color: #c586c0; }
        .type { color: #4ec9b0; }
        .function { color: #dcdcaa; }
        .number { color: #b5cea8; }
        .comment { color: #6a9955; }
        .string { color: #ce9178; }
        .operator { color: #d4d4d4; }
        .variable { color: #9cdcfe; }
        @keyframes fadeInUp {
            from {
                opacity: 0;
                transform: translateY(30px);
            }
            to {
                opacity: 1;
                transform: translateY(0);
            }
        }
        .animate-fadeInUp {
            animation: fadeInUp 0.8s ease-out;
        }
        .mermaid {
            display: flex;
            justify-content: center;
            margin: 2rem 0;
        }
    </style>
</head>
<body class="bg-gray-50">
    <!-- Hero Section -->
    <section class="hero-gradient text-white py-20 px-6">
        <div class="max-w-6xl mx-auto animate-fadeInUp">
            <div class="text-center">
                <h1 class="text-5xl md:text-6xl font-bold mb-6 serif-font">
                    <i class="fas fa-coins mr-4 text-yellow-300"></i>零钱兑换
                </h1>
                <p class="text-xl md:text-2xl mb-8 opacity-90">动态规划经典算法详解</p>
                <div class="flex justify-center gap-6 text-lg">
                    <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full">
                        <i class="fas fa-clock mr-2"></i>时间复杂度 O(n×m)
                    </span>
                    <span class="bg-white bg-opacity-20 px-4 py-2 rounded-full">
                        <i class="fas fa-memory mr-2"></i>空间复杂度 O(n)
                    </span>
                </div>
            </div>
        </div>
    </section>

    <!-- Main Content -->
    <main class="max-w-6xl mx-auto px-6 py-12">
        <!-- Problem Description -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.2s;">
            <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-question-circle text-purple-600 mr-3"></i>
                    <span class="gradient-text">题目描述</span>
                </h2>
                <div class="text-lg text-gray-700 leading-relaxed">
                    <p class="mb-4">给定不同面额的硬币 <code class="bg-purple-100 text-purple-800 px-2 py-1 rounded">coins</code> 和一个总金额 <code class="bg-purple-100 text-purple-800 px-2 py-1 rounded">amount</code>。</p>
                    <p class="mb-4">编写一个函数来计算可以凑成总金额所需的<strong class="text-purple-700">最少的硬币个数</strong>。如果没有任何一种硬币组合能组成总金额，返回 <code class="bg-red-100 text-red-800 px-2 py-1 rounded">-1</code>。</p>
                    <div class="bg-gradient-to-r from-purple-50 to-pink-50 p-6 rounded-xl mt-6">
                        <h3 class="font-bold text-xl mb-3 text-purple-800">
                            <i class="fas fa-lightbulb mr-2"></i>示例
                        </h3>
                        <p class="text-gray-700">
                            输入：<code class="bg-white px-2 py-1 rounded shadow-sm">coins = [1, 2, 5]</code>, 
                            <code class="bg-white px-2 py-1 rounded shadow-sm">amount = 11</code>
                        </p>
                        <p class="text-gray-700 mt-2">
                            输出：<code class="bg-green-100 text-green-800 px-2 py-1 rounded">3</code>
                        </p>
                        <p class="text-gray-600 mt-2 italic">
                            解释：11 = 5 + 5 + 1
                        </p>
                    </div>
                </div>
            </div>
        </section>

        <!-- Algorithm Visualization -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.4s;">
            <div class="bg-white rounded-2xl shadow-lg p-8">
                <h2 class="text-3xl font-bold mb-6 flex items-center">
                    <i class="fas fa-project-diagram text-purple-600 mr-3"></i>
                    <span class="gradient-text">算法可视化</span>
                </h2>
                <div class="mermaid">
                    graph TD
                        A[开始] --> B[初始化dp数组]
                        B --> C[dp[0] = 0]
                        C --> D[遍历每种硬币]
                        D --> E[对每个金额i计算最少硬币数]
                        E --> F{i >= coin?}
                        F -->|是| G[dp[i] = min(dp[i], dp[i-coin]+1)]
                        F -->|否| H[跳过]
                        G --> I{还有更多金额?}
                        H --> I
                        I -->|是| E
                        I -->|否| J{还有更多硬币?}
                        J -->|是| D
                        J -->|否| K[返回dp[amount]]
                        K --> L{dp[amount] < MAX?}
                        L -->|是| M[返回dp[amount]]
                        L -->|否| N[返回-1]
                        
                        style A fill:#667eea,stroke:#fff,stroke-width:2px,color:#fff
                        style M fill:#27c93f,stroke:#fff,stroke-width:2px,color:#fff
                        style N fill:#ff5f56,stroke:#fff,stroke-width:2px,color:#fff
                </div>
            </div>
        </section>

        <!-- Solution Approach -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.6s;">
            <div class="grid md:grid-cols-2 gap-8">
                <div class="bg-white rounded-2xl shadow-lg p-8 card-hover">
                    <h3 class="text-2xl font-bold mb-4 flex items-center">
                        <i class="fas fa-brain text-purple-600 mr-3"></i>
                        核心思想
                    </h3>
                    <ul class="space-y-3 text-gray-700">
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-green-500 mt-1 mr-3"></i>
                            <span>定义 <code class="bg-purple-100 text-purple-800 px-2 py-1 rounded text-sm">dp[i]</code> 为组成金额 i 所需的最少硬币数量</span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-green-500 mt-1 mr-3"></i>
                            <span>初始值设为较大数 <code class="bg-purple-100 text-purple-800 px-2 py-1 rounded text-sm">amount + 1</code></span>
                        </li>
                        <li class="flex items-start">
                            <i class="fas fa-check-circle text-green-500 mt-1 mr-3"></i>
                            <span>状态转移方程：<br><code class="bg-gray-100 px-3 py-2 rounded block mt-2 text-sm">dp[i] = min(dp[i], dp[i-coin] + 1)</code></span>
                        </li>
                    </ul>
                </div>
                
                <div class="bg-gradient-to-br from-purple-600 to-pink-600 text-white rounded-2xl shadow-lg p-8 card-hover">
                    <h3 class="text-2xl font-bold mb-4 flex items-center">
                        <i class="fas fa-chart-line mr-3"></i>
                        复杂度分析
                    </h3>
                    <div class="space-y-4">
                        <div class="bg-white bg-opacity-20 rounded-lg p-4">
                            <h4 class="font-semibold mb-2">
                                <i class="fas fa-clock mr-2"></i>时间复杂度
                            </h4>
                            <p class="text-lg">O(n × m)</p>
                            <p class="text-sm opacity-90 mt-1">n 为金额，m 为硬币种类数</p>
                        </div>
                        <div class="bg-white bg-opacity-20 rounded-lg p-4">
                            <h4 class="font-semibold mb-2">
                                <i class="fas fa-memory mr-2"></i>空间复杂度
                            </h4>
                            <p class="text-lg">O(n)</p>
                            <p class="text-sm opacity-90 mt-1">需要一个长度为 n+1 的数组</p>
                        </div>
                    </div>
                </div>
            </div>
        </section>

        <!-- Code Implementation -->
        <section class="mb-16 animate-fadeInUp" style="animation-delay: 0.8s;">
            <div class="bg-white rounded-2xl shadow-lg overflow-hidden">
                <div class="p-8 pb-0">
                    <h2 class="text-3xl font-bold mb-6 flex items-center">
                        <i class="fas fa-code text-purple-600 mr-3"></i>
                        <span class="gradient-text">代码实现</span>
                    </h2>
                </div>
                <div class="code-block mx-8 mb-8">
                    <div class="code-header">
                        <div class="code-dots">
                            <div class="dot dot-red"></div>
                            <div class="dot dot-yellow"></div>
                            <div class="dot dot-green"></div>
                        </div>
                        <span class="text-gray-400 text-sm">Java</span>
                    </div>
                    <pre><code><span class="keyword">public</span> <span class="type">int</span> <span class="function">coinChange</span>(<span class="type">int[]</span> <span class="variable">coins</span>, <span class="type">int</span> <span class="variable">amount</span>) {
    <span class="comment">// 定义一个较大的值作为初始值</span>
    <span class="type">int</span> <span class="variable">MAX</span> = <span class="variable">amount</span> + <span class="number">1</span>;
    
    <span class="comment">// 创建动态规划数组，dp[i]表示组成金额i所需的最少硬币数</span>
    <span class="type">int[]</span> <span class="variable">dp</span> = <span class="keyword">new</span> <span class="type">int</span>[<span class="variable">amount</span> + <span class="number">1</span>];
    
    <span class="comment">// 初始化dp数组，所有位置设为最大值</span>
    <span class="variable">Arrays</span>.<span class="function">fill</span>(<span class="variable">dp</span>, <span class="variable">MAX</span>);
    
    <span class="comment">// 组成金额0需要0个硬币</span>
    